#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_V 10 // 最大顶点数
#define MAX_E 20 // 最大边数

// 边结点结构（邻接多重表）
typedef struct EdgeNode
{
    int mark;               // 访问标记
    int ivex, jvex;         // 边的两个顶点索引
    struct EdgeNode *ilink; // 指向下一条依附于ivex的边
    struct EdgeNode *jlink; // 指向下一条依附于jvex的边
} EdgeNode;

// 顶点结构
typedef struct
{
    char *name;          // 顶点名称
    EdgeNode *firstEdge; // 指向第一条依附该顶点的边
} Vertex;

// 图结构（邻接多重表）
typedef struct
{
    Vertex vertices[MAX_V]; // 顶点数组
    EdgeNode edges[MAX_E];  // 边数组
    int vCount, eCount;     // 顶点数和边数
} AMLGraph;

// 1. 创建图
AMLGraph *createGraph()
{
    AMLGraph *g = (AMLGraph *)malloc(sizeof(AMLGraph));
    g->vCount = 0;
    g->eCount = 0;

    // 初始化顶点数组
    for (int i = 0; i < MAX_V; i++)
    {
        g->vertices[i].name = NULL;
        g->vertices[i].firstEdge = NULL;
    }

    // 初始化边数组
    for (int i = 0; i < MAX_E; i++)
    {
        g->edges[i].mark = 0;
        g->edges[i].ilink = g->edges[i].jlink = NULL;
    }

    return g;
}

// 2. 添加顶点
void addVertex(AMLGraph *g, const char *name)
{
    if (g->vCount >= MAX_V)
    {
        printf("Error: Graph is full\n");
        return;
    }
    g->vertices[g->vCount].name = strdup(name);
    g->vCount++;
}

// 3. 添加边（无向图）
void addEdge(AMLGraph *g, int v1, int v2)
{
    if (v1 < 0 || v1 >= g->vCount || v2 < 0 || v2 >= g->vCount)
    {
        printf("Error: Invalid vertex index\n");
        return;
    }
    if (g->eCount >= MAX_E)
    {
        printf("Error: Edge array is full\n");
        return;
    }

    // 创建新边
    EdgeNode *newEdge = &(g->edges[g->eCount++]);
    newEdge->ivex = v1;
    newEdge->jvex = v2;

    // 添加到v1的边链表（头插法）
    newEdge->ilink = g->vertices[v1].firstEdge;
    g->vertices[v1].firstEdge = newEdge;

    // 添加到v2的边链表（头插法）
    newEdge->jlink = g->vertices[v2].firstEdge;
    g->vertices[v2].firstEdge = newEdge;
}

// 4. 打印图
void printGraph(AMLGraph *g)
{
    printf("Adjacency Multilist (Undirected Graph):\n");

    // 打印顶点信息
    printf("Vertices:\n");
    for (int i = 0; i < g->vCount; i++)
    {
        printf("[%d] %s\n", i, g->vertices[i].name);
    }

    // 打印边信息
    printf("\nEdges:\n");
    for (int i = 0; i < g->eCount; i++)
    {
        printf("%s-%s\n",
               g->vertices[g->edges[i].ivex].name,
               g->vertices[g->edges[i].jvex].name);
    }

    // 打印邻接关系
    printf("\nAdjacency Lists:\n");
    for (int i = 0; i < g->vCount; i++)
    {
        printf("%s: ", g->vertices[i].name);
        EdgeNode *edge = g->vertices[i].firstEdge;
        while (edge)
        {
            // 确定当前顶点是ivex还是jvex
            int adjVertex = (edge->ivex == i) ? edge->jvex : edge->ivex;
            printf("%s ", g->vertices[adjVertex].name);

            // 移动到下一条边
            edge = (edge->ivex == i) ? edge->ilink : edge->jlink;
        }
        printf("\n");
    }
}

// 5. 销毁图
void destroyGraph(AMLGraph *g)
{
    if (!g)
        return;

    // 释放顶点名称
    for (int i = 0; i < g->vCount; i++)
    {
        free(g->vertices[i].name);
    }

    // 释放图结构
    free(g);
}

int main()
{
    // 创建图
    AMLGraph *g = createGraph();

    // 添加顶点
    addVertex(g, "A");
    addVertex(g, "B");
    addVertex(g, "C");
    addVertex(g, "D");

    // 添加边
    addEdge(g, 0, 1); // A-B
    addEdge(g, 0, 2); // A-C
    addEdge(g, 1, 3); // B-D
    addEdge(g, 2, 3); // C-D

    // 打印图
    printGraph(g);

    // 销毁图
    destroyGraph(g);

    return 0;
}